package com.geticsen.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/
public class Solution_1104 {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> result = new ArrayList<>();
        while (label > 0) {
            result.add(label);
            label = label >> 1;
        }
        Collections.reverse(result);
        int l, r, deep = result.size();
        for (int i = 0; i < deep; i++) {
            if ((deep & 1) != (i & 1)) continue;
            l = (1 << i);
            r = l + l - 1;
            result.set(i, r - result.get(i) + l);
        }
        return result;
    }
}
